#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
	vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k)
	{
		auto cmp = [&](const auto& o1, const auto& o2) { return nums1[o1.first] + nums2[o1.second] > nums1[o2.first] + nums2[o2.second]; };
		priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> q(cmp);
		for (int i = 0, len = min(max(size(nums1), size(nums2)), (size_t)k); i < len; i++) q.emplace(i, 0);

		vector<vector<int>> ans;
		int m = size(nums2);
		while (ans.size() < k and !q.empty()) {
			auto [a, b] = q.top();
			q.pop();
			ans.emplace_back(vector<int> { nums1[a], nums2[b] });
			if (b + 1 < m) q.emplace(a, b + 1);
		}
		return ans;
	}

private:
};

int main()
{
	[[maybe_unused]] Solution solution;
	return 0;
}
